A central processing unit (CPU) in a typical modern computer executes instructions stored in a main memory module. However, it may be a time consuming process to retrieve individual instructions from the main memory module. For this reason, modern computers typically include one or more instruction cache modules. These instruction cache modules are typically positioned closer to the CPU than the main memory module. Because the instruction cache modules are positioned closer to the CPU than the main memory module, the instruction cache modules may respond to requests for data faster than the main memory module. However, instruction cache modules typically hold less data than the main memory module. For this reason, not all instructions in a computer program may be stored in the instruction cache modules. When the CPU requests an instruction that is not in one of the instruction cache modules, it may be necessary to fetch the instruction from the main memory module, a comparatively time consuming operation. This is referred to as a “cache miss.”
Instruction cache modules may be implemented using various degrees of associativity. For example, in a fully associative cache module, any cache sector of the cache module may store any given memory address. In contrast, in a partially associative cache module, there are a limited number of cache sectors that may store a given memory address. In direct-mapped cache module, there is only one possible cache sector for any given memory address. Among these implementations, fully associative cache modules may have a lowest incidence of cache misses because there are many cache sectors that may store a given instruction. However, fully associative cache modules may be the most expensive to implement. This is because a typical fully associate cache module is implemented using parallel comparators. These comparators may be expensive to implement and may consume large amounts of space and power. The number of comparators in a fully associative cache module tends to increase as the size of the number of cache sectors in the fully associative cache module increases. Alternatively, a typical fully associative cache may be implemented using content-addressable memories (CAMs). However, CAMs are typically associated with slow access times and high power consumption.